package longestcommonsubstring

// long, short 是原始字符串，前者表示基准字符串，后者表示滑动窗口的字符串
// long_start 和 short_start 是各自的起始位置
// k 是当前窗口的长度
// 这个函数的作用是找到当前窗口的最大公共子串
// 调用方应该保证 a 和 b 的长度都大于 k, 且 a_start 和 b_start 都在字符串的范围内
func findMaxLength(a, b string, a_start, b_start int, k int) (int, int) {
	max := 0
	history := 0
	position := 0
	for i := 0; i < k; i++ {
		if a[a_start+i] == b[b_start+i] {
			max++
			if max > history {
				history = max
				position = a_start + i - history + 1
			}
		} else {
			max = 0
		}
	}
	return history, position
}

func longestCommonSubstringSlideWin(a, b string) string {
	// 1. 找到较短的字符串
	// 2. 对较短的字符串进行滑动窗口操作
	// 3. 在每个窗口中，找到最长公共子串
	// 4. 返回最长公共子串
	if len(a) < len(b) {
		a, b = b, a
	}

	maxSubStrLen := 0
	rightPosition := 0

	// 将long和short分别视为长窗口和短窗口
	// 将长窗口定位到x轴的正轴上，从0开始；将短窗口定位到x轴的负轴上，到0结束
	// 然后短窗口逐渐向右移动，直到与长窗口重叠，直到不再重合，告别
	// 例如，long = "abcdefghi", short = "cdefg"
	// 			   long = "abcdefghi" 0 1 2 3 4 5 6 7 8
	// short = "cdefg"    -4 -3 -2 -1 0
	// 			   long = "abcdefghi" 0 1 2 3 4 5 6 7 8
	// short = "cdefg"       -3 -2 -1 0 1
	// 			   long = "abcdefghi" 0 1 2 3 4 5 6 7 8
	// short = "cdefg"          -2 -1 0 1 2
	// 			   long = "abcdefghi" 0 1 2 3 4 5 6 7 8
	// short = "cdefg"             -1 0 1 2 3
	// 			   long = "abcdefghi" 0 1 2 3 4 5 6 7 8
	// short = "cdefg"                0 1 2 3 4
	// 			   long = "abcdefghi" 0 1 2 3 4 5 6 7 8
	// short = "cdefg"                  1 2 3 4 5
	// 			   long = "abcdefghi" 0 1 2 3 4 5 6 7 8
	// short = "cdefg"                    2 3 4 5 6
	// 			   long = "abcdefghi" 0 1 2 3 4 5 6 7 8
	// short = "cdefg"                      3 4 5 6 7
	// 			   long = "abcdefghi" 0 1 2 3 4 5 6 7 8
	// short = "cdefg"                        4 5 6 7 8
	// 			   long = "abcdefghi" 0 1 2 3 4 5 6 7 8
	// short = "cdefg"                          5 6 7 8 9
	// 			   long = "abcdefghi" 0 1 2 3 4 5 6 7 8
	// short = "cdefg"                            6 7 8 9 10
	// 			   long = "abcdefghi" 0 1 2 3 4 5 6 7 8
	// short = "cdefg"                              7 8 9 10 11
	// 			   long = "abcdefghi" 0 1 2 3 4 5 6 7 8
	// ...

	a_s := 0
	a_end := len(a) - 1
	for b_s := -len(b) + 1; b_s < len(a); b_s = b_s + 1 {
		// 计算当前窗口的长度
		// k 是当前窗口的长度
		// b_x a_x 是短窗口/长窗口的起始位置
		k, a_x, b_x := 0, 0, 0
		b_end := b_s + len(b) - 1
		if b_s < a_s {
			// 重叠窗口增大的过程
			k = b_end - a_s + 1
			a_x = a_s
			b_x = len(b) - k
		} else if b_s >= a_s && b_end <= a_end {
			// 完全重叠的过程
			k = b_end - b_s + 1
			a_x = b_s
			b_x = 0
		} else if b_end > a_end {
			// 重叠窗口减小的过程
			k = a_end - b_s + 1
			a_x = b_s
			b_x = 0
		}

		if k <= 0 {
			continue // should not reach here
		}

		// 在当前窗口中，找到最长公共子串
		max, idx := findMaxLength(a, b, a_x, b_x, k)
		if max > maxSubStrLen {
			maxSubStrLen = max
			rightPosition = idx
		}
	}
	return a[rightPosition : rightPosition+maxSubStrLen]
}

// 这个函数的作用是找到两个字符串的最长公共子串
// 1. 找到较短的字符串
// 2. 对较短的字符串进行滑动窗口操作
// 3. 在每个窗口中，找到最长公共子串
// 4. 返回最长公共子串
// 这个函数的时间复杂度是 O(n^2)，因为我们需要遍历字符串a的所有可能的子串，
// 对于每个子串，我们需要检查它是否在字符串b中存在，这个检查的时间复杂度是 O(n)，所以总的时间复杂度是 O(n^2)
// 这个函数的空间复杂度是 O(1)，因为我们只使用了常数级别的空间
